package com.leetcode.array_matrix;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/10/15 17:31
 */
public class BlackListNumber_710 {

    static class Solution {

        private Map<Integer, Integer> map;
        private int sz;
        private Random random;

        public Solution(int N, int[] blacklist) {
            map = new HashMap<>();
            random = new Random();
            sz = N - blacklist.length;
            for (int num : blacklist) {
                map.put(num, -1);
            }
            int last = N - 1;
            for (int num : blacklist) {
                if (num >= sz)
                    continue;
                while (map.containsKey(last--)) ;
                map.put(num, last + 1);
            }

        }

        public int pick() {
            int num = random.nextInt(sz);
            if (map.containsKey(num))
                num = map.get(num);
            return num;
        }
    }

}
